1. Field of the Invention
The present invention relates generally to rendering color in computer graphics software, and in particular, to a method, apparatus, and article of manufacture for quickly constructing a color-cube or mapping from a large set of specified colors to indices for a small set of previously defined colors.
2. Description of the Related Art
The perception of the different wavelengths of light may be represented using various color models. For example, in a color model that represents transmitted colors, red, green, and blue (RGB) are used to define the visible wavelengths. In a reflective color model, cyan (light blue), magenta (purplish-red), yellow, and black (CMYK) are used to define the visible wavelengths.
The RGB color model is often used for generating video on a display screen. In the RGB color model, each pixel on a display screen may be displayed as varying intensities of red, green, and blue dots. When all three colors are turned on high, white is produced. As intensities are equally lowered, shades of gray are derived. The base color of the screen appears when all dots are off. The CMYK color model is often used for printing images on a color printer. In theory, equal parts of cyan, magenta, and yellow ink make black. However, such blacks tend to have a muddy appearance when printed. Accordingly, a pure black fourth ink may be used in the CMYK( four color process (“K” for black).
In either color model, the number of available colors may be extremely large. For example, in the RGB color model, the red component alone may comprise hundreds or thousands of different intensities. The RGB color components are often described in terms of a vector consisting of the varying red, green, and blue components. Further, the vector components may be described in terms of how many bits are used to represent them. For example, a format such as 8-8-8 (for 8 bits each) or 6-5-5 (for 6 bits for red and 5 for green and blue) may be utilized. Thus, as the number of available colors increases, the number of bits required to store the color also increases. Accordingly, the storage and processing of such large images/files may be prohibitively large. Further, certain display devices, drivers, or video cards may have a limited capability such that it may only display a small set of predefined colors (e.g., 256 colors).
To save file space and increase processing capabilities, each pixel of an image may be associated or replaced with an index (also referred to as a color index). Such a color index corresponds to an entry in a table or color palette that contains the RGB color components for a small set of predefined colors (also referred to as index colors). This smaller set of predefined colors is usually a set of 256 colors, though it could be smaller or larger. Each index color in the predefined set may also be defined in vector terms, though it is always referred to by its index in the set. Because only an index is stored with the pixel, less memory is required to store the entire image.
A common problem in computer graphics is identifying and associating/substituting the appropriate color index for each pixel in an image. For example, in the prior art, the color of each pixel may be compared to each index color to determine the most similar index color. Consequently, for each pixel, numerous comparisons may be conducted.
Prior art methodologies may also provide a mapping of numerous RGB vector colors (that likely contain the colors utilized in an image) to the index color in the predefined set whose vector definition is closest to the desired vector color. For example (12,4,9) is closer to (0,0,0) than to (255,255,255), so (0,0,0) would be preferred. Once the mapping of RGB vector colors has been created, the color index for each color in an image may be easily determined.
To perform this mapping rapidly, prior art methods may build a table called a color cube. FIG. 1 illustrates a section view of a color cube. A color cube is an array with three-dimensions, indexed by the red (x-axis), green (y-axis), and blue (z-axis) vector components for all of the colors in a color set (e.g., all of the possible colors for a particular image). The value contained at each location in the array contains the color index into the set of predefined colors. This table is built once and reused over the life of a program or until the predefined colors are changed, whichever comes first. The size of this table can be described by the number of bits given to each vector. For example, a 4-4-4 table would give 4-bits to each red, green, and blue component, resulting in 24*24*24 (16*16*16) entries, i.e. 4096 entries. A 6-6-6 table would have about 64,000 entries, and an 8-8-8 table would have 16 million entries.
An issue that arises with respect to color cubes is with the creation of the mapping or determining which color cube entry contains which index. In the prior art, the values of the color cube are determined in two different ways. The first method is to determine which index color is the best match for the RGB represented by the vector entry into the color cube. Such a determination comprises comparing the vector color for each entry in the color cube to every index color. This has the advantage of being accurate but has the disadvantage of being expensive to compute.
The second method is to set some number of colors in the predefined color set along a regular pattern and then to fill in the cube using that same regular pattern. This has the advantage of being very cheap to compute but has the disadvantage of being less accurate since it will not allow a mapping to any of the unchangeable colors in the predefined set. Hence, there is a trade-off between accuracy and computational expense between these two methods.
There is also another trade-off between accuracy and computational expense in that the larger the cube is, the more accurate it is. For example a 6-6-6 cube will distinguish between (0,0,24) and (0,0,28) while a 4-4-4 cube will not.
The problem in the prior art is with attempting to minimize these trade-offs. It is desirable to have the most accurate and largest cube that can be held in memory. To obtain such a goal, the best match for every entry in the color cube should be determined. However, processing costs associated with performing numerous comparisons in a color cube can be high. For example, a brute force computation for finding the best matches for each entry in a 6-6-6 cube mapping to a set of 256 colors would require 67 million color comparisons, each of which involves five addition/subtraction operations and three multiplication operations. To expedite processing, a minimum amount of time should be dedicated to computing the values for that cube. To minimize processing, a color cube that is less accurate may be used.